package 数学作业.homework3.test1;

import java.util.Random;

public class 快速排序 {
    public static void main(String[] args) {
        Random ran = new Random();
        int[] arr = new int[100];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = ran.nextInt(101);
        }
        quickSort(arr,0,arr.length);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void quickSort(int[] arr,int left,int right){
        //确保最少有两个元素在排序
        if(right - left > 1) {
            int subscript = partition(arr, left, right);
            //左边都小于sub[ , )
            quickSort(arr, left, subscript);//注意这里的中间值是取
            //右边都大于sub[ , )
            quickSort(arr, subscript + 1, right);
        }
    }
    public static int partition(int[] arr,int left,int right){
        //确定作为比较值的下标，不要觉得这一步多余，这一步是为后面的优化打基础
        int index = right - 1;
        //等下即将返回的值
        int key = arr[right - 1]; //定义比较元素
        int begin = left;//左边从left开始
        int end = right - 1;//右边从right - 1下标开始

        while(begin < end){
            while(begin < end && arr[begin] <= key){
                begin++;
            }
            while(begin < end && arr[end] >= key){
                end--;
            }
            if(begin != end) {
                swap(arr, begin, end);
            }
        }
        if(begin != right-1){
            swap(arr, begin, right-1);
        }
        return begin;
    }
    /*
    public static int getMiddle(int[] array, int left, int right){
        int mid = left + ((right-left)>>1);
        if(array[left] < array[right-1]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right-1]){
                return right-1;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right-1]){
                return right-1;
            }else{
                return mid;
            }
        }
    }
     */
    public static void swap(int[] arr,int left,int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
}
